This disclosure relates generally to the field of manufacture semiconductor integrated circuits using triple-pattern lithography, and more particularly to methods, systems, and computer program products validating triple-pattern lithography layout decomposition.
In semiconductor fabrication processes, the resolution of a photoresist pattern begins to blur at about 45 nanometers (nm) half pitch. In order to provide semiconductor layers with smaller distances between adjacent patterns, with resorting to such expedients as extreme ultra violet (EUV) technology, double-patterning has been developed. In double-patterning, the layout of a single layer of an integrated circuit (IC) is decomposed into two masks. Then, there are two separate exposure and etching steps using each of the two masks separately. The advantages achieved with double-patterning have been extending using triple-patterning, wherein the layout is decomposed into three separate masks.
In multiple-patterning, such as double- and triple-patterning, design rules provide that polygons of the layout (of the same layer) that are separated from each other by less than a predetermined distance not be in the same mask. Graph theory has been applied to the analysis and validation of multiple-pattern decompositions. A given layout can be represented as a conflict graph CG=(V, G), wherein each vertex V represents a polygon (i.e., a circuit pattern) of the layout and an edge E is formed connecting two vertices, when the distance between two corresponding polygons is less than a minimum separation distance for clearly exposed patterns using a single photomask. A closed loop in a conflict graph with an even number of vertices can always be decomposed into two masks. Accordingly, a decomposition violation in double-patterning can be detected by the presence of a loop with an odd number of vertices in the conflict graph. However, decomposition validation in triple-patterning is a much more complex problem. In fact, the problem is NP-complete, which makes the problem not solvable in a reasonable amount of time.